// 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

// 示例:

// 输入: 3
// 输出: 5
// 解释:
// 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

//    1         3     3      2      1
//     \       /     /      / \      \
//      3     2     1      1   3      2
//     /     /       \                 \
//    2     1         2                 3
// 通过次数84,572提交次数122,361

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/unique-binary-search-trees
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//二叉搜索树种类 = 左子树种类 * 右子树种类
class Solution {
public:
    vector<int> result;
    int numTrees(int n) 
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        
        // 0  1  2  
        result.push_back(1);
        result.push_back(1);
        //主循环
        for(int i = 2; i <= n;i ++)
        {
            int res= 0 ;
            for(int j = 1 ; j <= i;j++)
            {
                res += result[i-j]* result[j-1];
            }
            result.push_back(res);
        }
        return result[n];
    }
};